Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and other digital devices. A variety of types of networks have been developed and implemented, including so-called "wide-area networks" (WANs), "local area networks" (LANs), which transfer information using diverse information transfer methodologies. Generally, LANs are implemented over relatively small geographical areas, such as within an individual office facility or the like, for transferring information within a particular office, company or similar type of organization. On the other hand, WANs are implemented over relatively large geographical areas, and may be used to transfer information between LANs, between devices that are not connected to LANs, and the like. WANs also include public networks, such as the Internet, which can carry information for a number of companies.
Several problems have arisen in connection with transfer of information over networks, particularly public networks. One problem is privacy, so that, if information to be transferred from a source device to a destination device over the network is intercepted by a third device, the intercepting device cannot determine what the actual information is. A second problem is tamper detection, so that, if information transferred from the source device to the destination device has been intercepted and tampered with by a third device, the tampering can be detected. A final problem is to ensure that information received by the destination device is "authentic," that is, that, if the information indicates that it has been transmitted by the source device, it (that is, the information) has actually be transmitted by the source device and not by a third device.
All of these problems are addressed by communication methodology as follows. When the source device has information ("INF") to be transferred, the source device first processes the information using a hash function to generate a hash value, that is, HASH(INF). Generally, a hash function takes an input value, in this case "INF," and generates therefrom an output value, in this case "HASH(INF)," that
(1) is of fixed length, even though the length of the input value may vary; PA1 (2) is such that the hash value generated using the hash function is highly likely to be unique; that is, that it is highly unlikely that different input values would "hash" to the same hash value; and PA1 (3) is such that, given the hash value "HASH(INF)," the input cannot be determined, with a high degree of probability, even if the hash function is known, that is, the hash function is not invertible.
With respect to condition (2) above, it is generally possible that different input values may hash to the same hash value, but if the number of possible hash values is made large enough, it would be extremely unlikely that two different input values would actually hash to the same hash value. If, for example, the length of the hash value is selected to be 128 digital data bits, then the number of possible different hash values would be 2.sup.128 (which corresponds to approximately 10.sup.38), which is an extremely large number. A number of hash functions are known, including, for example, those described in B. Schneier, "Applied Cryptography," 2d Edition (Wiley) (hereinafter "Schneier"), chapter 18, incorporated herein by reference. As will be described below, the destination device will be aware of the particular hash function used by the source device.
After generating the hash value HASH(INF), the source device will concatenate the hash value to the information to be transferred, thereby to generate an information packet "INF.vertline.HASH)(INF)"(where ".vertline." represents the concatenation operation). The "HASH(INF)" portion of the information packet represents a signature value for the information portion "INF."
Finally, the source device will encrypt the entire information packet INF.vertline.HASH(INF), thereby to generate a message packet E.sub.K.sub..sub.-- .sub.KEY (INF.vertline.HASH(INF)) to be transferred. The source device may use any encryption methodology, which will be known by the destination device. A number of encryption methodologies are known, including, for example, those as described in Parts II and III of Schneier, which is also incorporated herein by reference. Generally, encryption is performed in relation to one or more encryption key values (represented above by the subscript "E_KEY"). In one methodology, the source device can use a particular key value, which is also known by the destination device and which, as will be described below, will be used by the destination device in decrypting the message packet. In another methodology, which is known as the "public key/private key" encryption methodology, the source device will encrypt the information packet INF.vertline.HASH(INF) in relation to one value PRIV_S, termed the private key, to generate a message packet E.sub.PRIV.sub..sub.-- .sub.S (INF.vertline.HASH(INF)) for transfer to the destination device.
When the destination device receives a message packet which is purportedly from the particular source device, it (that is, the destination device) will initially perform a decryption operation to generate a decrypted information packet D.sub.D.sub..sub.-- .sub.KEY (E.sub.E.sub..sub.-- .sub.KEY (INF.vertline.HASH(INF))) using a decryption methodology and decryption key value "E_KEY" which will be related to the particular encryption methodology and encryption key value used by the source device. Decryption methodologies useful with the encryption techniques described in Parts II and III of Schneier are also described therein. If the source and destination devices are not using the public key/private key encryption methodology, the decryption key value "D_KEY" may be the same as the encryption key value "E_KEY" used by the source device in encrypting the operation. If the decryption key value "D_KEY" and the encryption key value "E_KEY" are the same, the encryption methodology is generally referred to as a symmetric cipher; an illustrative symmetric cipher is the Data Encryption Algorithm ("DEA") specified by the Data Encryption Standard ("DES") described in chapter 12 of Schneier. On the other hand, if the source and destination devices are using the public key/private key encryption methodology, then the key value used by the destination device would be the source device's public key value PUB_S, in which case the destination device would generate the decrypted information packet D.sub.PUB.sub..sub.-- .sub.S (INF.vertline.HASH(INF))).
The encryption of the message packet that is transferred between the source and destination devices ensures that the information in the packet will be private, to a high probability, particularly if the encryption and decryption keys are maintained in secrecy and not known by potential interceptors. However, encryption does not verify that the information packet has not been tampered with by a third device, nor does encryption by itself necessarily verify that the information packet was, in fact, transmitted by the particular source device which the destination device believes transmitted it. To accomplish this, the destination device will initially assume that the decrypted information packet D.sub.D.sub..sub.-- .sub.KEY (E.sub.E.sub..sub.-- .sub.KEY (INF.vertline.HASH(INF))) has the structure INF.vertline.HASH(INF)', that is, that it has an information packet with a hash value appended thereto, with the hash value being of the same length as the hash value of the information packet that was encrypted by the source device. Using the same hash function as the source device would use in generating the information packet, the destination device generates a hash value from the information portion of the packet, that is, HASH(INF'), and compares it to the hash value portion HASH(INF)'. If the two hash values are the same, then from property (2) of the hash function as described above, it would be extremely unlikely that the encrypted information packet transmitted by the source device would have been tampered with, since tampering would produce different information INF', which would hash to a different hash value. In addition, except in the unlikely event that a third device knew the encryption key used by the source device, if the destination device determines that the two hash values are the same, then the destination device can determine that the information packet originated from the source device.
A problem arises in connection with the methodology described above, in that encryption and decryption is very computation intensive, particularly for truly secure encryption and decryption methodologies. Since encryption and decryption are computation intensive, they may result in an increase in the latency, or delay, which is required to accomplish an information transfer, the latency being due to the time required to encrypt and decrypt the information to be transferred. The latency may be reduced by using expensive and powerful computers or special-purpose encryption and decryption hardware, which can add to the cost of the devices engaging in the information transfer. In addition, the time required to generate the encrypted and decrypted information packets increases linearly with the size of the information to be encrypted and decrypted. Accordingly, where privacy of the information is not a requirement, but where tamper detection and authenticity is needed, a communication methodology has been developed whereby only the hash value is encrypted, using the same encryption and decryption methodologies as described above. In that case, even if a third device knows which hash function and encryption methodology the presumed source device is using, if it (that is, the third device) does not know the source device's encryption key, it cannot generate an encrypted hash value which, when decrypted by the destination device would correspond to the hash value generated by the destination device for the information portion of the packet. Thus, thus communication methodology ensures authenticity, that is, that a packet presumably from a particular source device is actually from that source device, and that it has not been tampered with. However, the encryption and decryption operations required in this communication methodology can still require a significant amount of computation, particularly during a communication session during which the source device may transfer several information packets to the destination device, or during which the respective devices may transfer a number of information packets bidirectionally therebetween.